Vì là một không gian con của F q n {\displaystyle \mathbb {F} _{q}^{n}} , toàn bộ mã C (có kích thước lớn) có thể được biểu diễn chỉ bằng một hệ sinh gồm ít nhất mã tự (gọi là cơ sở trong đại số tuyến tính). Nếu ghép các mã tự này làm các hàng của ma trận G thì ma trận đó gọi là ma trận sinh của mã C. Khi G có dạng khối G = ( I k | A ) {\displaystyle G=(I_{k}|A)} , trong đó I k {\displaystyle I_{k}} là ma trận đơn vị k × k {\displaystyle k\times k} và A là một ma trận k × ( n − k ) {\displaystyle k\times (n-k)} , thì ta nói G nằm ở dạng chuẩn.

Ma trận H biểu diễn biến đổi tuyến tính ϕ : F q n → F q n − k {\displaystyle \phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n-k}} có hạt nhân là C được gọi là ma trận kiểm tra của C (còn được gọi là ma trận kiểm tra tính chẵn lẻ). Nếu C là mã với ma trận sinh G ở dạng chuẩn, G = (Ik | A), thì H = (−At | In − k) là ma trận kiểm tra của C. Mã sinh bởi H được gọi là mã đối ngẫu của C.

Tính chất tuyến tính đảm bảo khoảng cách Hamming nhỏ nhất d giữa mã tự c0 và bất kì mã tự c ≠ c0 nào là độc lập với c0. Điều này được suy ra từ tính chất hiệu c − c0 của hai mã tự trong C cũng là một mã tự (nghĩa là một phần tử của không gian C), và tính chất d(c, c0) = d(c − c0, 0). Theo các tính chất này,

min c ∈ C ,   c ≠ c 0 d ( c , c 0 ) = min c ∈ C , c ≠ c 0 d ( c − c 0 , 0 ) = min c ∈ C , c ≠ 0 d ( c , 0 ) = d . {\displaystyle \min _{c\in C,\ c\neq c_{0}}d(c,c_{0})=\min _{c\in C,c\neq c_{0}}d(c-c_{0},0)=\min _{c\in C,c\neq 0}d(c,0)=d.}

Nói cách khác, để xác định khoảng cách nhỏ nhất giữa các mã tự của một mã tuyến tính, chỉ cần xét khoảng cách giữa các mã tự khác không và mã tự không. Mã tự khác không có trọng lượng nhỏ nhất chính là mã tự gần mã tự không nhất và trọng số đó chính là khoảng cách nhỏ nhất.

Khoảng cách d của một mã tuyến tính C cũng bằng số nhỏ nhất các cột phụ thuộc tuyến tính của ma trận kiểm tra H.

Chứng minh: Xét c là mã tự có trọng số nhỏ nhất. Theo định nghĩa, H ⋅ c T = 0 {\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}} nên các cột H i {\displaystyle {\boldsymbol {H_{i}}}} với c i ≠ 0 {\displaystyle c_{i}\neq 0} phụ thuộc tuyến tính. Vì vậy số cột nhỏ nhất phụ thuộc tuyến tính là nhỏ hơn hoặc bằng d.

Mặt khác xét một tập hợp nhỏ nhất các cột phụ thuộc tuyến tính { H j | j ∈ S } {\displaystyle \{{\boldsymbol {H_{j}}}|j\in S\}} trong đó S {\displaystyle S} là tập hợp các chỉ số các cột này. ∑ i = 1 n ( c i ⋅ H i ) = ∑ j ∈ S ( c j ⋅ H j ) + ∑ j ∉ S ( c j ⋅ H j ) = 0 {\displaystyle \sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})=\sum _{j\in S}(c_{j}\cdot {\boldsymbol {H_{j}}})+\sum _{j\notin S}(c_{j}\cdot {\boldsymbol {H_{j}}})={\boldsymbol {0}}} . Xét vectơ c ′ {\displaystyle {\boldsymbol {c'}}} sao cho c j ′ = 0 {\displaystyle c_{j}^{'}=0} nếu j ∉ S {\displaystyle j\notin S} . Ta nhận thấy c ′ ∈ C {\displaystyle {\boldsymbol {c'}}\in C} vì H ⋅ c ′ T = 0 {\displaystyle {\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}} . Do đó ta có d ≤ w t ( c ′ ) {\displaystyle d\leq wt({\boldsymbol {c'}})} , chính là số nhỏ nhất các cột phụ thuộc tuyến tính của H {\displaystyle {\boldsymbol {H}}} .

Như vậy, ta thu được kết quả cần chứng minh.